package com.myc.subjects.binarytreeandrecurtion;

import com.myc.subjects.utils.TreeUtils;

/**
 * LeetCode题号：226
 *
 * 翻转二叉树
 *
 * 翻转一棵二叉树。
 * 示例：
 * 输入：
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 *
 * 输出：
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/invert-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Fanzhuanerchashu {

    public static void main(String[] args) {
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode9 = new TreeNode(9);

        treeNode4.left = treeNode2;
        treeNode4.right = treeNode7;
        treeNode2.left= treeNode1;
        treeNode2.right = treeNode3;
        treeNode7.left = treeNode6;
        treeNode7.right = treeNode9;

        TreeUtils.showTree(treeNode4);
        System.out.println();
        Fanzhuanerchashu f = new Fanzhuanerchashu();
        TreeUtils.showTree(f.invertTree1(treeNode4));
        System.out.println();
        TreeUtils.showTree(f.invertTree2(treeNode4));
    }

    /**
     * 方法一：先序遍历
     * 时间复杂度：O(log^n)
     * 先处理当前节点的左右子树，再处理左右子树的左右子树，自顶向下翻转
     */
    public TreeNode invertTree1(TreeNode root) {
        //退出递归条件
        if(root == null) return null;

        //交换左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        //左右子树分别递归调用
        invertTree1(root.left);
        invertTree1(root.right);

        //返回根节点
        return root;
    }

    /**
     * 方法二：后序遍历
     * 时间复杂度：O(log^n)
     * 先处理左右子树，自底向上翻转
     */
    public TreeNode invertTree2(TreeNode root){
        if(root == null) return null;

        //左右子树分别递归调用
        TreeNode left = invertTree2(root.left);
        TreeNode right = invertTree2(root.right);

        //交换左右子树
        root.left = right;
        root.right = left;

        return root;
    }

    //官方题解
    public TreeNode invertTreeOfficial(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTreeOfficial(root.left);
        TreeNode right = invertTreeOfficial(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

}

/**
 * 总结：需要熟练掌握二叉树的深度优先遍历的三种方式：先序遍历，中序遍历，后序遍历
 */
